package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName InsertSort
 * @Description 插入排序（直接插入排序）--升序
 * @Detail 元素：
 *              1、插入的数
 *                  首先是数组的第二个元素进行插入，其次是第三个，以此类推
 *              2、被插入的索引
 *                  首先被插入的索引是0
 *              3、两层嵌套循环
 *                  内层是为了找到索引位置
 *                  外层是为了插入数据，外层循环只需要循环数组长度-1次
 * @Author MyPC
 * @Date 2020/7/18
 * @Version 1.0
 */
public class InsertSort {
    public static void main(String[] args) {
        int arr[]={15,2,4,8,1,4,5,18,6,7};
        for(int i=1;i<arr.length;i++){
            //插入的数据，第一次循环时是数组的第二个元素，以此类推
            int insertValue=arr[i];
            //被插入的数的索引
            int index=i-1;
            //如果被插入的索引大于0（防止索引越界）且插入的数比被插入的数小，则被插入的数要向右移动,这里不能确定要循环多少次，所以使用while循环
            while (index>=0 && insertValue < arr[index]){
                arr[index+1]=arr[index];
                index--;
            }
            //找到位置，进行插入
            arr[index+1]=insertValue;
        }
        System.out.println(Arrays.toString(arr));
    }
}
